#include <stdio.h>
#include <stdlib.h>

typedef long int *vetor;
typedef	long int v_elm;
//#define vetor int*

vetor gera_vetor(int n);
vetor copia_vetor(vetor v, int n);
void apaga_vetor(vetor v);
void printv(char *s,vetor v, int n);

long int selection_sort(vetor v, int n);
long int merge_sort(vetor v, int p,int r);
long int insertion_sort(vetor v, int n);
long int quick_sort(vetor a, int p,int r);

int main(int argc, char **argv) {
	int n;
	long int m,q,s,i;
	vetor v;
	vetor vn,vq,vs,vi;

	if(argc <= 1)
		puts("Erro! Parametro N faltante!");

	if((n=atoi(argv[1]))<1)
		puts("Erro! Vetor muito pequeno!!");

	v=gera_vetor(n);

	vn=copia_vetor(v,n);
	vq=copia_vetor(v,n);
	vs=copia_vetor(v,n);
	vi=copia_vetor(v,n);

	//printv("Vetor original",v, n);

	printf("Algoritmo\tTempos\n");
	m=merge_sort(vn,0,n-1);
	printf("Merge Sort\t%ld\n",m);
	//printv("Merge sort",vn, n);

	q=quick_sort(vq,0,n-1);
	printf("Quick Sort\t%ld\n",q);
	//printv("Quick sort",vq,n);

	s=selection_sort(vs,n);
	printf("Selection Sort\t%ld\n",s);
	//printv("Selection sort",vs,n);

	i=insertion_sort(vi,n);
	printf("Insertion Sort\t%ld\n",i);
	//printv("Insertion sort",vi,n);

	apaga_vetor(v);
	apaga_vetor(vn);
	apaga_vetor(vq);
	apaga_vetor(vs);
	apaga_vetor(vi);

	return 0;
}

void printv(char *s,vetor v, int n) {
	int i;
	printf("%s\n",s);
	for(i=0;i<n;i++)
		printf("%ld",v[i]);
	printf("\n\n");
}

vetor gera_vetor(int n) {
	int i;
	vetor v=(vetor) malloc((sizeof (v_elm)) * n);
	if (!v) abort();
	for(i=0;i<n;i++) {
		v_elm k=random();
		v[i]=k;
	}
	return v;
}

vetor copia_vetor(vetor v,int n) {
	int i;
	vetor u=(vetor) malloc((sizeof (int)) * n);
		if (!v) abort();
	for(i=0;i<n;i++)
		u[i]=v[i];

	return u;
}

void apaga_vetor(vetor v) {
	free(v);
}

long int selection_sort(vetor v, int n){
	int i,j,min;
	long cont=1;
	v_elm x;
	for(i=0;i<n-1;i++) {
		min=i;
		for(j=i+1;j<n;j++) {
			cont++; //benchmark
			if (v[min] > v[j])
				min=j;
		}
		x=v[i];
		v[i]=v[min];
		v[min]=x;
	}
	return cont;
}

long int insertion_sort(vetor v, int n){
	int i,j;
	v_elm x;
	long int cont=1; //benchmark
	for(i=1;i<n;i++) {
		x=v[i];
		j=i-1;
		while(j>=0 && v[j]>x) {
			v[j+1]=v[j];
			j--;
			cont++; //benchmark
		}
		v[j+1]=x;
	}

	return cont;
}

long int merge(vetor v, int p, int q, int r) {
	int i,j,k;
	v_elm b[r-p+1];

	long int cont=1; //benchmark
	i=p,j=q,k=0;

	while(i<q && j<=r) {
		cont++;
		if(v[i]<=v[j])
			b[k++]=v[i++];
		else b[k++]=v[j++];

	}

	while(i<q) {
		cont++;
		b[k++]=v[i++];
	}

	while (j<=r) {
		cont++;
		b[k++]=v[j++];
	}

	for(i=0;i<k;i++) {
		cont++;
		v[p++]=b[i];
	}

	return cont;
}

long int merge_sort(vetor v, int p,int r) {
	long int i=0,j=0,k=0;
	if(p<r) {
		int q=(p+r)/2;
		i=merge_sort(v,p,q);
		j=merge_sort(v,q+1,r);
		k=merge(v,p,q+1,r);
	}
	return i+j+k;
}

int partition(vetor a, int p, int r, long int *cont) {
	int i,j;
	v_elm x;
	i=p+1,j=r;
	while(i<=j) {
		(*cont)++; //benchmark
		if (a[i]<=a[p])
			i++;
		else if (a[j]>a[p])
			j--;
		else {
			x=a[i],a[i]=a[j],a[j]=x; //troca
			i++;
			j--;
		}
	}
	x=a[p],a[p]=a[j],a[j]=x;
	return j;
}

long int quick_sort(vetor a, int p,int r) {
	long int i=0,j=0,cont=1;
	if(p<r) {
		int q=partition(a,p,r,&cont);
		i=quick_sort(a,p,q-1);
		j=quick_sort(a,q+1,r);
	}
	return i+j+cont;
}
